package likou.offer;

import java.util.ArrayList;
import java.util.List;

/**
 * @Info:
 * @Author: 唐小尊
 * @Date: 2020/8/23  19:09
 */
public class _41 {
    static link root;

    static class link {
        link next;
        int val;

        public link(int val) {
            this.val = val;
        }
    }

    static int length;

    /**
     * initialize your data structure here.
     */
    public static void MedianFinder() {
        length = 0;
    }

    public static void addNum(int num) {
        length++;
        if (root == null) {
            root = new link(num);
        } else {
            if (num>root.val){
                link temp = root;
                while (temp.next != null && num > temp.next.val) {
                    temp = temp.next;
                }
                link now = new link(num);
                now.next = temp.next;
                temp.next = now;
            }else {
                link now = new link(num);
                now.next = root;
                root = now;
            }
        }
    }
//1-》2-》3-》4-》5-》6，length=6
    public static double findMedian() {
        link temp = root;
        int i = 0;
        if (length % 2 == 0) {
            while (i<length/2-1){
                temp=temp.next;
                i++;
            }
            return (double) (temp.val + temp.next.val) / 2;
        } else {
            while (i<length/2){
                temp=temp.next;
                i++;
            }
            return (double) temp.val;
        }
    }

    public static void main(String[] args) {
        MedianFinder();
        addNum(6);
        System.out.println(findMedian());
        addNum(10);
        System.out.println(findMedian());
        addNum(2);
        System.out.println(findMedian());
        addNum(6);
        System.out.println(findMedian());
        addNum(5);
        System.out.println(findMedian());
        addNum(0);
        System.out.println(findMedian());
        addNum(6);
        System.out.println(findMedian());
        addNum(3);
        System.out.println(findMedian());
        addNum(1);
        System.out.println(findMedian());
        addNum(0);
        System.out.println(findMedian());
        addNum(0);
        System.out.println(findMedian());

    }
//[null,null,6.0,null,8.0,null,10.0,null,6.0,null,2.0,null,4.0,null,6.0,null,5.5,null,5.0,null,2.5,null,0.0]
//[null,null,6.0,null,8.0,null,6.0 ,null,6.0,null,6.0,null,5.5,null,6.0,null,5.5,null,5.0,null,4.0,null,3.0]
}
